/**
 * @(#) TestSubmallsetString.java Apr 3, 2010 11:49:33 AM
 * Copyright (C) 2009 GeeYee Inc. 60606, Chicago, IL, USA
 * All right reserved
 */
package old;

import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;

/**
 * You r given a large string of characters lets call it Sbig. Then there is a
 * small set of characters lets call it Ssmall. You have to find smallest
 * substring of Sbig which contains all characters in Ssmall.
 * 
 */
public class TestSubmallsetString {
	static LinkedHashMap map = new LinkedHashMap();

	static int[][] vvv;

	public static int calc()

	{
		int total = 0;
		int min = 99999;
		int index = -1;
		for (int i = 0; i < vvv.length; i++)

		{
			for (int j = 0; j < vvv[i].length; j++)

			{
				for (int k = j + 1; k < vvv[i].length; k++)

				{
					total += Math.abs(vvv[i][j] - vvv[i][k]);

				}

			}
			if (total < min)

			{
				index = i;
				min = total;

			}
			total = 0;

		}
		return index;

	}

	public static void fillCrossProductArray(String s, String sStr)

	{
		int colIndex = 0;
		int rowPointer = 0;
		int tLength = vvv.length;
		int counter = 0;
		int tmp = 0;
		for (int xx = 0; xx < sStr.length(); ++xx) // start with "a" level

		{
			Object[] l = ((HashSet) map.get(sStr.charAt(xx))).toArray();
			for (int i1 = 0; i1 < l.length; i1++) // loop array

			{
				tmp = tLength / l.length;
				for (int kk = rowPointer; kk < vvv.length; kk += tLength) // loop
																			// rows

				{
					while (counter < tmp)

					{
						vvv[kk + counter][colIndex] = (Integer) l[i1];
						counter++;

					}
					counter = 0;

				}
				rowPointer += tLength / l.length;

			}
			tLength = tLength / l.length;
			rowPointer = 0;
			colIndex++;

		}

	}

	public static void init(String s, String sStr)

	{
		for (int i = 0; i < sStr.length(); i++)

		{
			map.put(sStr.charAt(i), new LinkedHashSet());

		}
		for (int i = 0; i < sStr.length(); i++)

		{
			for (int j = 0; j < s.length(); j++)

			{
				if (s.charAt(j) == sStr.charAt(i))

				{
					((LinkedHashSet) map.get(sStr.charAt(i))).add(j);

				}

			}

		}
		Iterator it = map.keySet().iterator();
		int numOfRow = 1;
		HashSet hs = null;
		for (int i = 0; i < map.size(); i++)

		{
			hs = ((LinkedHashSet) map.get(it.next()));
			System.out.println(hs);
			numOfRow *= hs.size();

		}
		vvv = new int[numOfRow][sStr.length()];

	}

	public static void test(String s, String sStr)

	{
		String origS = s;

		init(s, sStr);
		fillCrossProductArray(s, sStr);
		int idx = calc();

		System.out.println(s);
		System.out.println(sStr);
		for (int i = 0; i < vvv.length; i++)

		{
			for (int j = 0; j < vvv[i].length; j++)

			{
				System.out.print(vvv[i][j] + ",");

			}
			System.out.println();

		}
		System.out.println("Shortest path");
		int begin = vvv[idx][0];
		int end = vvv[idx][0];
		int j = 0;
		for (; j < vvv[idx].length; j++) {
			if (vvv[idx][j] > end)
				end = vvv[idx][j];
			if (vvv[idx][j] < begin)
				begin = vvv[idx][j];
			System.out.print(vvv[idx][j] + ",");

		}

		System.out.println(origS.substring(begin, end + 1));

	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		TestSubmallsetString.test("hello what are you doing", "eto");
	}

}
